package codetop.microsoft.S33;

import java.util.Arrays;

/**
 * @Author: 18362
 * @Create: 2022-09-04 22:21:12 星期日
 */
class Solution {

    private boolean flag = true;

    public boolean verifyPostorder(int[] postorder) {
        if (postorder.length <= 1)
            return true;
        int[] inorder = new int[postorder.length];
        System.arraycopy(postorder, 0, inorder, 0, postorder.length);
        Arrays.sort(inorder);
        verify(inorder, postorder, 0, inorder.length-1, 0, postorder.length-1);
        return flag;
    }

    private void verify(int[] inorder, int[] postorder, int inl, int inr, int postl, int postr) {
        if (inl > inr || !flag)
            return;
        int k = -1;
        for (int i=inl; i<=inr; ++i) {
            if (inorder[i] == postorder[postr]) {
                k = i;
                break;
            }
        }
        if (k < 0) {
            flag = false;
            return;
        }
        verify(inorder, postorder, inl, k - 1, postl, postl + k - inl - 1);
        verify(inorder, postorder, k + 1, inr, postl + k - inl, postr - 1);
    }
}